package com.sunny;

import java.util.ArrayList;
import java.util.List;

/**
 * 堆排注意0位不用，从1位开始
 */
public class HeapSort {

    public static void main(String[] args) {

        HeapSort heapSort = new HeapSort();
        int[] arr = {-1,2,1,8,5,3,9,0,2};
        heapSort.build(arr);
        List<Integer> list = heapSort.sort(arr);
        list.forEach(System.out::println);

    }

    public List<Integer> sort(int[] arr){
        ArrayList<Integer> list = new ArrayList<>();
        int n = arr.length-1;
        while (n > 0) {
//            print(arr, n);
            list.add(arr[1]);
            swap(arr, 1, n);
//            print(arr, n);
            n--;
            adjust(arr, 1, n);
        }
        return list;
    }

    public void print(int[] arr, int n){
        for(int i=1;i<=n;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    public void build(int[] arr){
        int n = arr.length-1;
        for(int i=n/2;i>=1;i--){
//            System.out.println(i+":");
            adjust(arr, i, n);
        }
//        for(int i=1;i<arr.length;i++){
//            System.out.print(arr[i]+" ");
//        }
//        System.out.println();
    }

    public void adjust(int[] arr, int ind, int n){
        int tmp = arr[ind];
        int cur = ind;
        int next = 2*cur;
        while (next<=n){
//            System.out.println(cur+" "+next);
            if(next+1<=n && arr[next] > arr[next+1]){
                next++;
            }
            if(tmp <= arr[next]){
                break;
            }
            arr[cur] = arr[next];
            cur = next;
            next = 2*cur;
        }
        arr[cur] = tmp;
    }

    public void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

}
